import java.util.Arrays;
import java.util.Set;

public class Day7 {



    public static void main(String[] args) {

    }
    //36.有效的数独
    boolean[][] row1,col1;
    boolean[][][] grid1;
    public boolean isValidSudoku(char[][] board) {
        col1 = new boolean[9][10];
        row1 = new boolean[9][10];
        grid1 = new boolean[3][3][10];
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                if(board[i][j] == '.') {
                    continue;
                }
                int tmp = Integer.parseInt(board[i][j]+"");
                if(col1[j][tmp] == true || row1[i][tmp] == true || grid1[i/3][j/3][tmp] == true) {
                    return false;
                }else {
                    col1[j][tmp] = row1[i][tmp] = true;
                    grid1[i/3][j/3][tmp] = true;
                }
            }
        }
        return true;
    }
    //37.解数独
    boolean[][] row,col;
    boolean[][][] grid;
    boolean bool;
    public void solveSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                if(board[i][j] != '.') {
                    int k = board[i][j]-'0';
                    row[i][k] = col[j][k] = grid[i/3][j/3][k]=true;
                }
            }
        }
        dfs(board,0,0);
    }
    public void dfs(char[][] board,int m,int n) {
        if(n >=9 && m >=8) {
            bool = true;
            return;
        }
        if(n>=9 && m < 8) {
            m+=1;
            n=0;
        }
        //0 <= m <= 8  0<=n<=8
        if(board[m][n] != '.') {
            if(bool) return;
            dfs(board,m,n+1);
        }else {
            for(int k=1;k<=9;k++) {//k代表可以填入的数字
                if(row[m][k] ==false && col[n][k]==false&&grid[m/3][n/3][k]==false) {
                    board[m][n] = (char)(k+'0');
                    row[m][k] = col[n][k] = grid[m/3][n/3][k]=true;
                    dfs(board,m,n+1);
                    if(bool) return;
                    board[m][n] = '.';
                    row[m][k] = col[n][k] = grid[m/3][n/3][k]=false;
                }
            }
        }
    }



}
